package com.lw.leetcode.hash.b;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/28 9:26
 */
public class HasAllCodes {

    public static void main(String[] args) {
        HasAllCodes test = new HasAllCodes();

        // true
//        String str = "00110110";
//        int k = 1;

        // true
//        String str = "0110";
//        int k = 1;

        // false
        String str = "0110";
        int k = 2;

        boolean b = test.hasAllCodes(str, k);

        System.out.println(b);
    }

    public boolean hasAllCodes(String s, int k) {
        int length = s.length();
        if (length < (k << 1)) {
            return false;
        }
        Set<Integer> set = new HashSet<>();
        int item = 0;
        for (int i = 0; i < k; i++) {
            item = (item << 1) + s.charAt(i) - '0';
        }
        set.add(item);
        for (int i = k; i < length; i++) {
            item = ((item - ((s.charAt(i - k) - '0') << (k - 1))) << 1) + s.charAt(i) - '0';
            set.add(item);
        }
        return set.size() == (1 << k);
    }

}
